package formal.queueStack;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author DengYuan2
 * @create 2021-01-29 20:29
 */
public class M_739 {
    public static void main(String[] args) {
        int[] a = {73, 74, 75, 71, 69, 72, 76,73};
        int[] res = dailyTemperatures(a);
        System.out.println(Arrays.toString(res));
    }

    /**
     * 我的思路：stack中存放当前值和其在数组中的下标；新加入的值大于栈顶元素时就弹出栈顶值进行处理
     * @param T
     * @return
     */
    public static int[] dailyTemperatures(int[] T) {
        int[] res = new int[T.length];
        Stack<int[]> stack = new Stack<>();
        for (int i = 0; i < T.length; i++) {
            int val = T[i];
            if (stack.isEmpty()){
                stack.push(new int[]{val,i});
            }
            while (!stack.isEmpty()&&stack.peek()[0]<val){
                int[] pop = stack.pop();
                res[pop[1]]=i-pop[1];
            }
            stack.push(new int[]{val,i});
        }
        //剩余的为0，不必处理
        return res;
    }

    /**
     * 大神的写法-栈中只需要存储索引即可
     * @param T
     * @return
     */
    public static int[] dailyTemperatures2(int[] T) {
        int length = T.length;
        int[] res = new int[length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < length; i++) {
            while (!stack.isEmpty()&&T[stack.peek()]<T[i]){
                Integer cur = stack.pop();
                res[cur]=i-cur;
            }
            stack.push(i);
        }
        return res;
    }
}
